import java.util.Arrays;


    //给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
    //示例 1:
    //输入: nums = [2,2,3,4]
    //输出: 3
    //解释:有效的组合是:
    //2,3,4 (使用第一个 2)
    //2,3,4 (使用第二个 2)
    //2,2,3
   public class Solution {
        public int triangleNumber(int[] nums) {
            int a = 0, b = 0, c = 0;
            //1.优化：排序
            Arrays.sort(nums);
            //2.利用双指针解决问题
            int ret = 0, n = nums.length;
            for (int i = n - 1; i >= 2; i--) {//先固定最大的数
                //利用双指针快速统计出符合要求的三元组的个数
                int left = 0, right = i - 1;
                while (left < right) {
                    if (nums[left] + nums[right] > nums[i]) {
                        ret += right - left;
                        right--;
                    } else {
                        left++;
                    }
                }

            }
            return ret;


        }
        public static void main(String[] args) {
            Solution solution = new Solution();
            int[] nums = {2,2,3,4};
            int ste = solution.triangleNumber(nums);

            System.out.println(ste);
        }
    }





